package LeetCode.month01.day29;

import java.util.*;

public class No2813 {
    static long max = Integer.MIN_VALUE;

    public static void main(String[] args) {
        System.out.println(findMaximumElegance(new int[][]{{1,3},{3,3},{10,2},{10,1}}, 2));
    }


    public static long findMaximumElegance(int[][] items, int k) {
        Arrays.sort(items,(a,b)-> b[0]-a[0]);
        Set<Integer> set = new HashSet<>();
        Deque<Integer> duplicate = new ArrayDeque<>();
        long ans = Integer.MIN_VALUE;
        long total = 0;
        for (int i = 0; i < items.length; i++) {
            int profit = items[i][0];
            int category = items[i][1];
            if(i<k){
                total+= profit;
                if(!set.add(category)){
                    duplicate.push(profit);
                }
            }else if(!duplicate.isEmpty()&&set.add(category)){
                total+=profit-duplicate.pop();
            }
            ans = Math.max(ans,total+(long)set.size()*set.size());
        }
        return ans;
    }
//    public static long findMaximumElegance(int[][] items, int k) {
//        HashMap<Integer,Integer> map = new HashMap<>();
//        dfs(map,items,k,0,0,0);
//        return max;
//    }
//
//    private static void dfs(HashMap<Integer, Integer> map, int[][] items, int k, int index,int num,int value) {
//        if(num==k){
//            System.out.println(max);
//            long n = map.size();
//            max = Math.max(value+n*n,max);
//            System.out.println("num = " + num);
//            System.out.println("n = " + n);
//            System.out.println("value = " + value);
//            System.out.println("map = " + map);
//            System.out.println("max = " + max);
//            return;
//        }
//        for (int i = index; i < items.length; i++) {
//            map.put(items[i][1],map.getOrDefault(items[i][1],0)+items[i][0]);
//            value+=items[i][0];
//            num++;
//            dfs(map,items,k,i+1,num,value);
//            if(map.get(items[i][1])==items[i][0]) map.remove(items[i][1]);
//            else map.put(items[i][1],map.get(items[i][1])-items[i][0]);
//            num--;
//            value-=items[i][0];
//        }
//    }

}
